home *** CD-ROM | disk | FTP | other *** search
/ AGA Toolkit '97 / The AGA Toolkit '97.iso / miscellaneous / science / maths / calc / source / listfunc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-09-07  |  11.3 KB  |  550 lines
  1. /*
  2.  * Copyright (c) 1993 David I. Bell
  3.  * Permission is granted to use, distribute, or modify this source,
  4.  * provided that this copyright notice remains intact.
  5.  *
  6.  * List handling routines.
  7.  * Lists can be composed of any types of values, mixed if desired.
  8.  * Lists are doubly linked so that elements can be inserted or
  9.  * deleted efficiently at any point in the list.  A pointer is
  10.  * kept to the most recently indexed element so that sequential
  11.  * accesses are fast.
  12.  */
  13.  
  14. #include "value.h"
  15.  
  16.  
  17. static LISTELEM *elemalloc MATH_PROTO((void));
  18. static LISTELEM *listelement MATH_PROTO((LIST *lp, long index));
  19. static void elemfree MATH_PROTO((LISTELEM *ep));
  20. static void removelistelement MATH_PROTO((LIST *lp, LISTELEM *ep));
  21.  
  22.  
  23. /*
  24.  * Free lists for list headers and list elements.
  25.  */
  26. static FREELIST    headerfreelist = {
  27.     sizeof(LIST),        /* size of list header */
  28.     20            /* number of free headers to keep */
  29. };
  30.  
  31. static FREELIST elementfreelist = {
  32.     sizeof(LISTELEM),    /* size of list element */
  33.     1000            /* number of free list elements to keep */
  34. };
  35.  
  36.  
  37. /*
  38.  * Insert an element before the first element of a list.
  39.  */
  40. void
  41. insertlistfirst(lp, vp)
  42.     LIST *lp;        /* list to put element onto */
  43.     VALUE *vp;        /* value to be inserted */
  44. {
  45.     LISTELEM *ep;        /* list element */
  46.  
  47.     ep = elemalloc();
  48.     copyvalue(vp, &ep->e_value);
  49.     if (lp->l_count == 0)
  50.         lp->l_last = ep;
  51.     else {
  52.         lp->l_cacheindex++;
  53.         lp->l_first->e_prev = ep;
  54.         ep->e_next = lp->l_first;
  55.     }
  56.     lp->l_first = ep;
  57.     lp->l_count++;
  58. }
  59.  
  60.  
  61. /*
  62.  * Insert an element after the last element of a list.
  63.  */
  64. void
  65. insertlistlast(lp, vp)
  66.     LIST *lp;        /* list to put element onto */
  67.     VALUE *vp;        /* value to be inserted */
  68. {
  69.     LISTELEM *ep;        /* list element */
  70.  
  71.     ep = elemalloc();
  72.     copyvalue(vp, &ep->e_value);
  73.     if (lp->l_count == 0)
  74.         lp->l_first = ep;
  75.     else {
  76.         lp->l_last->e_next = ep;
  77.         ep->e_prev = lp->l_last;
  78.     }
  79.     lp->l_last = ep;
  80.     lp->l_count++;
  81. }
  82.  
  83.  
  84. /*
  85.  * Insert an element into the middle of list at the given index (zero based).
  86.  * The specified index will select the new element, so existing elements
  87.  * at or beyond the index will be shifted down one position.  It is legal
  88.  * to specify an index which is right at the end of the list, in which
  89.  * case the element is appended to the list.
  90.  */
  91. void
  92. insertlistmiddle(lp, index, vp)
  93.     LIST *lp;        /* list to put element onto */
  94.     long index;        /* element number to insert in front of */
  95.     VALUE *vp;        /* value to be inserted */
  96. {
  97.     LISTELEM *ep;        /* list element */
  98.     LISTELEM *oldep;    /* old list element at desired index */
  99.  
  100.     if (index == 0) {
  101.         insertlistfirst(lp, vp);
  102.         return;
  103.     }
  104.     if (index == lp->l_count) {
  105.         insertlistlast(lp, vp);
  106.         return;
  107.     }
  108.     oldep = NULL;
  109.     if ((index >= 0) && (index < lp->l_count))
  110.         oldep = listelement(lp, index);
  111.     if (oldep == NULL)
  112.         math_error("Index out of bounds for list insertion");
  113.     ep = elemalloc();
  114.     copyvalue(vp, &ep->e_value);
  115.     ep->e_next = oldep;
  116.     ep->e_prev = oldep->e_prev;
  117.     ep->e_prev->e_next = ep;
  118.     oldep->e_prev = ep;
  119.     lp->l_cache = ep;
  120.     lp->l_cacheindex = index;
  121.     lp->l_count++;
  122. }
  123.  
  124.  
  125. /*
  126.  * Remove the first element from a list, returning its value.
  127.  * Returns the null value if no more elements exist.
  128.  */
  129. void
  130. removelistfirst(lp, vp)
  131.     LIST *lp;        /* list to have element removed */
  132.     VALUE *vp;        /* location of the value */
  133. {
  134.     if (lp->l_count == 0) {
  135.         vp->v_type = V_NULL;
  136.         return;
  137.     }
  138.     *vp = lp->l_first->e_value;
  139.     lp->l_first->e_value.v_type = V_NULL;
  140.     removelistelement(lp, lp->l_first);
  141. }
  142.  
  143.  
  144. /*
  145.  * Remove the last element from a list, returning its value.
  146.  * Returns the null value if no more elements exist.
  147.  */
  148. void
  149. removelistlast(lp, vp)
  150.     LIST *lp;        /* list to have element removed */
  151.     VALUE *vp;        /* location of the value */
  152. {
  153.     if (lp->l_count == 0) {
  154.         vp->v_type = V_NULL;
  155.         return;
  156.     }
  157.     *vp = lp->l_last->e_value;
  158.     lp->l_last->e_value.v_type = V_NULL;
  159.     removelistelement(lp, lp->l_last);
  160. }
  161.  
  162.  
  163. /*
  164.  * Remove the element with the given index from a list, returning its value.
  165.  */
  166. void
  167. removelistmiddle(lp, index, vp)
  168.     LIST *lp;        /* list to have element removed */
  169.     long index;        /* list element to be removed */
  170.     VALUE *vp;        /* location of the value */
  171. {
  172.     LISTELEM *ep;        /* element being removed */
  173.  
  174.     ep = NULL;
  175.     if ((index >= 0) && (index < lp->l_count))
  176.         ep = listelement(lp, index);
  177.     if (ep == NULL)
  178.         math_error("Index out of bounds for list deletion");
  179.     *vp = ep->e_value;
  180.     ep->e_value.v_type = V_NULL;
  181.     removelistelement(lp, ep);
  182. }
  183.  
  184.  
  185. /*
  186.  * Remove an arbitrary element from a list.
  187.  * The value contained in the element is freed.
  188.  */
  189. static void
  190. removelistelement(lp, ep)
  191.     register LIST *lp;        /* list header */
  192.     register LISTELEM *ep;        /* list element to remove */
  193. {
  194.     if ((ep == lp->l_cache) || ((ep != lp->l_first) && (ep != lp->l_last)))
  195.         lp->l_cache = NULL;
  196.     if (ep->e_next)
  197.         ep->e_next->e_prev = ep->e_prev;
  198.     if (ep->e_prev)
  199.         ep->e_prev->e_next = ep->e_next;
  200.     if (ep == lp->l_first) {
  201.         lp->l_first = ep->e_next;
  202.         lp->l_cacheindex--;
  203.     }
  204.     if (ep == lp->l_last)
  205.         lp->l_last = ep->e_prev;
  206.     lp->l_count--;
  207.     elemfree(ep);
  208. }
  209.  
  210.  
  211. /*
  212.  * Search a list for the specified value starting at the specified index.
  213.  * Returns the element number (zero based) of the found value, or -1 if
  214.  * the value was not found.
  215.  */
  216. long
  217. listsearch(lp, vp, index)
  218.     LIST *lp;
  219.     VALUE *vp;
  220.     long index;
  221. {
  222.     register LISTELEM *ep;
  223.  
  224.     if (index < 0)
  225.         index = 0;
  226.     ep = listelement(lp, index);
  227.     while (ep) {
  228.         if (!comparevalue(&ep->e_value, vp)) {
  229.             lp->l_cache = ep;
  230.             lp->l_cacheindex = index;
  231.             return index;
  232.         }
  233.         ep = ep->e_next;
  234.         index++;
  235.     }
  236.     return -1;
  237. }
  238.  
  239.  
  240. /*
  241.  * Search a list backwards for the specified value starting at the
  242.  * specified index.  Returns the element number (zero based) of the
  243.  * found value, or -1 if the value was not found.
  244.  */
  245. long
  246. listrsearch(lp, vp, index)
  247.     LIST *lp;
  248.     VALUE *vp;
  249.     long index;
  250. {
  251.     register LISTELEM *ep;
  252.  
  253.     if (index >= lp->l_count)
  254.         index = lp->l_count - 1;
  255.     ep = listelement(lp, index);
  256.     while (ep) {
  257.         if (!comparevalue(&ep->e_value, vp)) {
  258.             lp->l_cache = ep;
  259.             lp->l_cacheindex = index;
  260.             return index;
  261.         }
  262.         ep = ep->e_prev;
  263.         index--;
  264.     }
  265.     return -1;
  266. }
  267.  
  268.  
  269. /*
  270.  * Index into a list and return the address for the value corresponding
  271.  * to that index.  Returns NULL if the element does not exist.
  272.  */
  273. VALUE *
  274. listfindex(lp, index)
  275.     LIST *lp;        /* list to index into */
  276.     long index;        /* index of desired element */
  277. {
  278.     LISTELEM *ep;
  279.  
  280.     ep = listelement(lp, index);
  281.     if (ep == NULL)
  282.         return NULL;
  283.     return &ep->e_value;
  284. }
  285.  
  286.  
  287. /*
  288.  * Return the element at a specified index number of a list.
  289.  * The list is indexed starting at zero, and negative indices
  290.  * indicate to index from the end of the list.  This routine finds
  291.  * the element by chaining through the list from the closest one
  292.  * of the first, last, and cached elements.  Returns NULL if the
  293.  * element does not exist.
  294.  */
  295. static LISTELEM *
  296. listelement(lp, index)
  297.     register LIST *lp;    /* list to index into */
  298.     long index;        /* index of desired element */
  299. {
  300.     register LISTELEM *ep;    /* current list element */
  301.     long dist;        /* distance to element */
  302.     long temp;        /* temporary distance */
  303.     BOOL forward;        /* TRUE if need to walk forwards */
  304.  
  305.     if (index < 0)
  306.         index += lp->l_count;
  307.     if ((index < 0) || (index >= lp->l_count))
  308.         return NULL;
  309.     /*
  310.      * Check quick special cases first.
  311.      */
  312.     if (index == 0)
  313.         return lp->l_first;
  314.     if (index == 1)
  315.         return lp->l_first->e_next;
  316.     if (index == lp->l_count - 1)
  317.         return lp->l_last;
  318.     if ((index == lp->l_cacheindex) && lp->l_cache)
  319.         return lp->l_cache;
  320.     /*
  321.      * Calculate whether it is better to go forwards from
  322.      * the first element or backwards from the last element.
  323.      */
  324.     forward = ((index * 2) <= lp->l_count);
  325.     if (forward) {
  326.         dist = index;
  327.         ep = lp->l_first;
  328.     } else {
  329.         dist = (lp->l_count - 1) - index;
  330.         ep = lp->l_last;
  331.     }
  332.     /*
  333.      * Now see if we have a cached element and if so, whether or
  334.      * not the distance from it is better than the above distance.
  335.      */
  336.     if (lp->l_cache) {
  337.         temp = index - lp->l_cacheindex;
  338.         if ((temp >= 0) && (temp < dist)) {
  339.             dist = temp;
  340.             ep = lp->l_cache;
  341.             forward = TRUE;
  342.         }
  343.         if ((temp < 0) && (-temp < dist)) {
  344.             dist = -temp;
  345.             ep = lp->l_cache;
  346.             forward = FALSE;
  347.         }
  348.     }
  349.     /*
  350.      * Now walk forwards or backwards from the selected element
  351.      * until we reach the correct element.  Cache the location of
  352.      * the found element for future use.
  353.      */
  354.     if (forward) {
  355.         while (dist-- > 0)
  356.             ep = ep->e_next;
  357.     } else {
  358.         while (dist-- > 0)
  359.             ep = ep->e_prev;
  360.     }
  361.     lp->l_cache = ep;
  362.     lp->l_cacheindex = index;
  363.     return ep;
  364. }
  365.  
  366.  
  367. /*
  368.  * Compare two lists to see if they are identical.
  369.  * Returns TRUE if they are different.
  370.  */
  371. BOOL
  372. listcmp(lp1, lp2)
  373.     LIST *lp1, *lp2;
  374. {
  375.     LISTELEM *e1, *e2;
  376.     long count;
  377.  
  378.     if (lp1 == lp2)
  379.         return FALSE;
  380.     if (lp1->l_count != lp2->l_count)
  381.         return TRUE;
  382.     e1 = lp1->l_first;
  383.     e2 = lp2->l_first;
  384.     count = lp1->l_count;
  385.     while (count-- > 0) {
  386.         if (comparevalue(&e1->e_value, &e2->e_value))
  387.             return TRUE;
  388.         e1 = e1->e_next;
  389.         e2 = e2->e_next;
  390.     }
  391.     return FALSE;
  392. }
  393.  
  394.  
  395. /*
  396.  * Copy a list
  397.  */
  398. LIST *
  399. listcopy(oldlp)
  400.     LIST *oldlp;
  401. {
  402.     LIST *lp;
  403.     LISTELEM *oldep;
  404.  
  405.     lp = listalloc();
  406.     oldep = oldlp->l_first;
  407.     while (oldep) {
  408.         insertlistlast(lp, &oldep->e_value);
  409.         oldep = oldep->e_next;
  410.     }
  411.     return lp;
  412. }
  413.  
  414.  
  415. /*
  416.  * Allocate an element for a list.
  417.  */
  418. static LISTELEM *
  419. elemalloc()
  420. {
  421.     LISTELEM *ep;
  422.  
  423.     ep = (LISTELEM *) allocitem(&elementfreelist);
  424.     if (ep == NULL)
  425.         math_error("Cannot allocate list element");
  426.     ep->e_next = NULL;
  427.     ep->e_prev = NULL;
  428.     ep->e_value.v_type = V_NULL;
  429.     return ep;
  430. }
  431.  
  432.  
  433. /*
  434.  * Free a list element, along with any contained value.
  435.  */
  436. static void
  437. elemfree(ep)
  438.     LISTELEM *ep;
  439. {
  440.     if (ep->e_value.v_type != V_NULL)
  441.         freevalue(&ep->e_value);
  442.     freeitem(&elementfreelist, (FREEITEM *) ep);
  443. }
  444.  
  445.  
  446. /*
  447.  * Allocate a new list header.
  448.  */
  449. LIST *
  450. listalloc()
  451. {
  452.     register LIST *lp;
  453.  
  454.     lp = (LIST *) allocitem(&headerfreelist);
  455.     if (lp == NULL)
  456.         math_error("Cannot allocate list header");
  457.     lp->l_first = NULL;
  458.     lp->l_last = NULL;
  459.     lp->l_cache = NULL;
  460.     lp->l_cacheindex = 0;
  461.     lp->l_count = 0;
  462.     return lp;
  463. }
  464.  
  465.  
  466. /*
  467.  * Free a list header, along with all of its list elements.
  468.  */
  469. void
  470. listfree(lp)
  471.     register LIST *lp;
  472. {
  473.     register LISTELEM *ep;
  474.  
  475.     while (lp->l_count-- > 0) {
  476.         ep = lp->l_first;
  477.         lp->l_first = ep->e_next;
  478.         elemfree(ep);
  479.     }
  480.     freeitem(&headerfreelist, (FREEITEM *) lp);
  481. }
  482.  
  483.  
  484. /*
  485.  * Print out a list along with the specified number of its elements.
  486.  * The elements are printed out in shortened form.
  487.  */
  488. void
  489. listprint(lp, max_print)
  490.     LIST *lp;
  491.     long max_print;
  492. {
  493.     long count;
  494.     long index;
  495.     LISTELEM *ep;
  496.  
  497.     if (max_print > lp->l_count)
  498.         max_print = lp->l_count;
  499.     count = 0;
  500.     ep = lp->l_first;
  501.     index = lp->l_count;
  502.     while (index-- > 0) {
  503.         if ((ep->e_value.v_type != V_NUM) ||
  504.             (!qiszero(ep->e_value.v_num)))
  505.                 count++;
  506.         ep = ep->e_next;
  507.     }
  508.     if (max_print > 0)
  509.         math_str("\n");
  510.     math_fmt("list (%ld element%s, %ld nonzero)", lp->l_count,
  511.         ((lp->l_count == 1) ? "" : "s"), count);
  512.     if (max_print <= 0)
  513.         return;
  514.  
  515.     /*
  516.      * Walk through the first few list elements, printing their
  517.      * value in short and unambiguous format.
  518.      */
  519.     math_str(":\n");
  520.     ep = lp->l_first;
  521.     for (index = 0; index < max_print; index++) {
  522.         math_fmt("  [[%ld]] = ", index);
  523.         printvalue(&ep->e_value, PRINT_SHORT | PRINT_UNAMBIG);
  524.         math_str("\n");
  525.         ep = ep->e_next;
  526.     }
  527.     if (max_print < lp->l_count)
  528.         math_str("  ...\n");
  529. }
  530.  
  531.  
  532. /*
  533.  * Return a trivial hash value for a list.
  534.  */
  535. HASH
  536. listhash(lp)
  537.     LIST *lp;
  538. {
  539.     HASH hash;
  540.  
  541.     hash = lp->l_count * 600011;
  542.     if (lp->l_count > 0)
  543.         hash = hash * 600043 + hashvalue(&lp->l_first->e_value);
  544.     if (lp->l_count > 1)
  545.         hash = hash * 600053 + hashvalue(&lp->l_last->e_value);
  546.     return hash;
  547. }
  548.  
  549. /* END CODE */
  550.